public class ThreadTree {
    public static void main(String[] args) {

        ThreadTreeNode root=new ThreadTreeNode(1);
        ThreadTreeNode node1=new ThreadTreeNode(3);
        ThreadTreeNode node2=new ThreadTreeNode(6);
        ThreadTreeNode node3=new ThreadTreeNode(8);
        ThreadTreeNode node4=new ThreadTreeNode(10);
        ThreadTreeNode node5=new ThreadTreeNode(14);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node1.setRight(node4);
        node2.setLeft(node5);
        Thread thread=new Thread(root);
        thread.PrePrint();
        System.out.println("线索化二叉树");
        thread.ThreadMethod(root);
        System.out.println("中序遍历线索化二叉树");
        thread.MidOrderPrintThread();
    }
}

class Thread{
    private ThreadTreeNode root;
    private ThreadTreeNode pre=null;//前驱
    public Thread(ThreadTreeNode root){
        this.root=root;
    }
    //前序遍历
    public void PrePrint(){
        if(root==null){
            System.out.println("此时树是空的");
            return;
        }else{
            root.PreOrderPrint();
        }

    }
    //中序线索化二叉树
    public void ThreadMethod(ThreadTreeNode node){//查看结点的前驱和后继
        //看看这个结点是指向左子树就srtLeftType就为0，没有左子树就，指向前驱设为1
        //看看这个结点是指向右子树就srtRightType就为0，没有右子树就，指向前驱设为1
        //该结点的前驱在该节点设置，后继在下个结点设置
        if(node==null){
            return;
        }
        //左子树线索化
        ThreadMethod(node.getLeft());
        //根节点线索化
        if(node.getLeft()==null){
            //没有左子树就指向前驱
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //结点的后继
        if(pre!=null && pre.getRight()==null){
            //后继放到下个结点进行处理
            pre.setRight(node);//node是pre的后一个结点，这里将上个节点的后继放在下个结点进行处理
            pre.setRightType(1);
        }
        pre=node;//移动pre指针

        //右子树线索化
        ThreadMethod(node.getRight());


    }
    //中序遍历线索化二叉树--左根右
    public void MidOrderPrintThread() {
        ThreadTreeNode tempNode = root;
        while (tempNode != null) {
            while (tempNode.getLeftType() == 0) {
                //指向的是左子树
                tempNode = tempNode.left;
            }
            //此时指向的是前驱，即没有左子树了
            //根
            System.out.print(tempNode.getNum()+" ");
            //右
            while (tempNode.getRightType() == 1) {
                tempNode = tempNode.getRight();
                System.out.println(tempNode.getNum()+" ");
            }
            tempNode = tempNode.getRight();//到了下一个叶子结点，重复遍历

        }
    }


}
class ThreadTreeNode{
    public int num;//编号
    public ThreadTreeNode left;//左子树
    public ThreadTreeNode right;//右子树
    public int leftType=0;//左子树的前驱
    public int rightType=0;//右子树的前驱


    //遍历二叉树--前序遍历
    public void PreOrderPrint(){
        //根左右---根就是指当前节点
        System.out.println(this.toString());//根

        if(this.left!=null){
            this.left.PreOrderPrint();
        }
        if(this.right!=null){
            this.right.PreOrderPrint();
        }

    }



    public ThreadTreeNode(int num){
        this.num=num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setLeft(ThreadTreeNode left) {
        this.left = left;
    }

    public ThreadTreeNode getLeft() {
        return left;
    }

    public void setRight(ThreadTreeNode right) {
        this.right = right;
    }

    public ThreadTreeNode getRight() {
        return right;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getRightType() {
        return rightType;
    }

    @Override
    public String toString() {
        return "ThreadTreeNode{" +
                "num=" + num +
                '}';
    }
}